package Bi_Tree.level_traversal;

import Bi_Tree.TreeNode;

import java.sql.Connection;
import java.util.*;

//给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
public class lc107 {
    //在原先层次的基础上将其结果反转即可
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();
        if(root==null){
            return result;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> smalllist =new ArrayList<>();
            int len= queue.size();
            while(len>0){
                TreeNode node= queue.poll();
                smalllist.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
                len--;
            }
            result.add(smalllist);
        }
        /*List<List<Integer>> result1 = new ArrayList<>();
        for (int i = result.size() - 1; i >= 0; i-- ) {
            result1.add(result.get(i));
        }
        return  result1;*/
       Collections.reverse(result);
        return result;
    }

}
